package com.company;

/**
 * @ClassName:
 * @author:
 * @Description:
 * @Date
 **/
//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

public class TopK {
    public interface Queue<E> {
        void enqueue(E e);
        E dequeue();
        E getFront();
        int getSize();
        boolean isEmpty();
    }
    public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

        private MaxHeap<E> maxHeap;

        public PriorityQueue() {
            maxHeap = new MaxHeap<>();
        }

        @Override
        public void enqueue(E e) {
            maxHeap.add(e);
        }

        @Override
        public E dequeue() {
            return maxHeap.extractMax();
        }

        @Override
        public E getFront() {
            return maxHeap.findMax();
        }

        @Override
        public int getSize() {
            return maxHeap.size();
        }

        @Override
        public boolean isEmpty() {
            return maxHeap.isEmpty();
        }
    }
    public class Array<E> {
        private E[] data;
        private int size;

        /**
         * @param capacity
         */
        public Array(int capacity) {
            data = (E[]) new Object[capacity];
            size = 0;
        }

        public Array() {
            this(10);
        }

        public Array(E[] arr) {
            data = (E[]) new Object[arr.length];
            for (int i = 0; i < arr.length; i++) {
                data[i] = arr[i];
                size = arr.length;
            }
        }

        public int getSize() {
            return size;
        }

        public int getCapacity() {
            return data.length;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 向数组尾部添加元素
         *
         * @param e
         */
        public void addLast(E e) {
            add(size, e);
        }

        /**
         * 向数组头部添加元素
         *
         * @param e
         */
        public void addFirst(E e) {
            add(0, e);
        }

        /**
         * 向任意位置添加元素  大于index位置的每个元素都向后移动
         *
         * @param index
         * @param e
         */
        public void add(int index, E e) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("Add failed");
            }
            if (size == data.length) {
                resize(2 * data.length);
            }
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }

        private void resize(int newCapacity) {
            E[] newData = (E[]) new Object[newCapacity];
            for (int i = 0; i < newData.length; i++) {
                newData[i] = data[i];
            }
            data = newData;
        }

        /**
         * 删除任意位置的元素 并返回被删除的元素
         * 被删除的元素后的每个元素向前移动一个
         *
         * @return
         */
        public E remove(int index) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("index error");
            }
            E ret = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size--;
            data[size] = null;
            if (size == data.length / 4 && data.length / 2 != 0) {
                resize(data.length / 2);
            }
            return ret;
        }

        public E removeFirst() {
            return remove(0);
        }

        public E removeLast() {
            return remove(size - 1);
        }

        public void removeElement(E e) {
            if (find(e) != -1) {
                remove(find(e));
            }
        }

        /**
         * 修改index位置元素的值
         *
         * @param index
         * @param e
         */
        public void set(int index, E e) {
            data[index] = e;
        }


        /**
         * 查找数组中是否包含某一元素
         *
         * @param e
         * @return
         */
        public boolean contains(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)) {
                    return true;
                }
            }
            return false;
        }

        public E get(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("index out of bound");
            }
            return data[index];
        }


        /**
         * 查找数组中的某个元素并返回索引
         *
         * @param e
         * @return
         */
        public int find(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)) {
                    return i;
                }
            }
            return -1;
        }

        public void swap(int i, int j) {
            if (i < 0 || i >= size || j < 0 || j <= size) {
                throw new IllegalArgumentException("index out of bound");
            }
            E temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("Array size:" + this.size + ", capacity:" + this.getCapacity() + " ");
            builder.append("[ ");
            for (int i = 0; i < size; i++) {
                builder.append(data[i] + " ");
            }
            builder.append("]");
            return builder.toString();
        }
    }

    public class MaxHeap<E extends Comparable<E>> {
        private Array<E> data;

        public MaxHeap(int capacity) {
            data = new Array<>(capacity);
        }

        public MaxHeap() {
            data = new Array<>();
        }

        //将任意数组转换成堆
        public MaxHeap(E[] arr) {
            data = new Array<>(arr);
            //从第一个非叶子节点开始
            for (int i = parent(arr.length - 1); i >= 0; i--) {
                //下沉元素
                siftDown(i);
            }
        }

        public int size() {
            return data.getSize();
        }

        public boolean isEmpty() {
            return data.isEmpty();
        }

        //返回完全二叉树的数组表示中，一个索引表示的元素的父节点的索引
        private int parent(int index) {
            if (index == 0) {
                throw new IllegalArgumentException("index 0 doesn't have parent");
            }
            return (index - 1) / 2;
        }

        //返回完全二叉树的数组表示中，一个索引表示的元素的左孩子的索引
        private int leftChild(int index) {
            return index * 2 + 1;
        }

        //返回完全二叉树的数组表示中，一个索引表示的元素的右孩子的索引
        private int rightChild(int index) {
            return index * 2 + 2;
        }

        //向堆中添加元素
        public void add(E e) {
            //先将元素加到数组的末尾
            data.addLast(e);
            //元素上浮
            siftUp(data.getSize() - 1);
        }

        private void siftUp(int i) {
            //如果i>0并且索引i位置的元素大于它的父节点，就交换它和它的父节点，此时索引等于父节点的索引
            while (i > 0 && data.get(parent(i)).compareTo(data.get(i)) < 0) {
                data.swap(i, parent(i));
                i = parent(i);
            }
        }

        //看堆中最大的元素
        public E findMax() {
            if (data.getSize() == 0) {
                throw new IllegalArgumentException("heap is empty");
            }
            return data.get(0);
        }

        //取出堆中最大的元素
        public E extractMax() {
            E ret = findMax();
            data.swap(0, data.getSize() - 1);
            data.removeLast();
            siftDown(0);
            return ret;
        }

        private void siftDown(int i) {
            while (leftChild(i) < data.getSize()) {
                //在此轮循环中，data[i]和data[j]交换位置
                int j = leftChild(i);
                if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                    //j=rightChild(i);
                    j++;
                    //data[j]是leftChild和rightChild中的最大值
                }
                if (data.get(i).compareTo(data.get(j)) >= 0) {
                    break;
                }
                data.swap(i, j);
                i = j;
            }
        }

        //取出最大的元素并替换成e
        public E replace(E e) {
            E ret = findMax();
            data.set(0, e);
            siftDown(0);
            return ret;
        }


    }


    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            queue.enqueue(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (!queue.isEmpty() && arr[i] < queue.getFront()) {
                queue.dequeue();
                queue.enqueue(arr[i]);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.dequeue();
        }
        return res;
    }
}
